The present disclosure relates to decompression of a compressed data stream. The present disclosure relates to decompression of compressed data having a length and distance, or offset, encoding, such as the LZ77 compression technique. The disclosure includes decompression hardware which is described as a functional block to be integrated into an Application Specific Integrated Circuit (ASIC) as part of a System on Chip (SOC). The decompression hardware can be applied to decompression of data stored in main memory of a computer system. The decompression hardware may make use of existing hardware components. The decompression technique is applicable to a software, or hybrid software and hardware implementation.
LZ77 is a known compression technique which removes redundancy from a byte stream by replacing a string of bytes that repeats within the input stream with a reference, or pointer, to a prior instance of the same bytes. The reference is encoded as a <length, distance> pair, where length is the number of bytes being replaced and distance is the number of bytes prior in the input stream where the prior instance occurred. The output of LZ77 compression is a sequence of symbols which represent either literal bytes or <length, distance> pairs.
The LZ77 technique lends itself to a sequential decompression, as the bytes produced by any symbol may depend on the bytes produced by any prior symbol. The sequential nature of the decompression process imposes a limit on the rate that decompression can be performed.
It is estimated that LZ77 decompression implemented in software may achieve about 1 GB/s.
Some operating systems provide a feature of using a portion of main memory as a swap device. There is a need to compress data for storing in the swap device, for example, in cases where the amount of data to be stored is large and it is desired to limit the size of main memory. The swap device is used to store data that has not been recently used. The swap device can be used to compress and store data that has not been recently used, as data that is less likely to be used in the near future. Subsequently, when a page fault occurs, the needed data is obtained from the swap device by way of decompression processing. It is desired to make such decompression processing as fast as possible in order to avoid incurring a significant penalty that would negate the benefit of using compression to store data in main memory.
Various approaches have been devised to speed up decompression, including decompression of data that has been compressed using the LZ77 compression technique. In an example, a decoder is configured to decode up to 4 codewords at a time, guaranteeing minimum throughput of 4F symbols or Bytes/second, where F is the clock frequency.
However, for doing decompression of data maintained in a portion of main memory, it is considered necessary to obtain a much higher decompression rate than known approaches, together with maximizing bandwidth. Example embodiments of the disclosed invention are expected to achieve 16 GB/s decompression rate.